package org.nowcoder.leetcode.BTree;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;

/**
 * Title  : 235. Lowest Common Ancestor of a Binary Search Tree
 * Source : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
 * Author : XrazYang
 * Date   : 2024-04-20
 */

public class LeetCode_235 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        ArrayDeque<TreeNode> sta = new ArrayDeque<>();
        Map<Integer, TreeNode> father = new HashMap<>();
        father.put(root.val, null);
        sta.push(root);
        while (!sta.isEmpty()) {
            TreeNode node = sta.pop();
            if (node.left != null) {
                sta.push(node.left);
                father.put(node.left.val, node);
            }
            if (node.right != null) {
                sta.push(node.right);
                father.put(node.right.val, node);
            }
        }
        //找到共同的父结点
        TreeNode node;
        while (p != null) {
            node = q;
            while (node != null) {
                if (node.val == p.val) {
                    return node;
                }
                node = father.get(node.val);
            }
            p = father.get(p.val);
        }
        return null;
    }
}
